\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\(1 \le n \le {10}^5\)，\(1 \le a_i \le {10}^{12}\)，\(0 \le b_i < a_i\)，保证所有
\(a_i\) 的最小公倍数不超过 \({10}^{18}\)

\begin{lstlisting}
const int N = 1e5 + 10;
ll n , s[N] , p[N];
ll mul(ll a,ll b,ll mod)
{
	ll res = 0;
	while(b)
	{
		if(b & 1) res = (res + a) % mod;
		a = (a + a) % mod;
		b >>= 1;
	}
	return res;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x = 1 , y = 0;
		return a;
	}
	ll g = exgcd(b , a % b , x , y);
	ll tp = x;
	x = y , y = tp - a / b * y;
	return g;
}
ll EX_CRT(ll *s , ll *p , ll n)
{
	ll x , y , k , LCM = p[1] , ans = s[1];
	rep(i , 2 , n)
	{
		ll a = LCM , b = p[i] , c = (s[i] - ans % b + b) % b;
		ll g = exgcd(a , b , x , y) , bg = b / g;
		if(c % g != 0) return -1;
		x = mul(x , c / g , bg);
		ans += x * LCM , LCM *= bg;
		ans = (ans % LCM + LCM) % LCM;
	}
	return ans;
}
signed main()
{
	cin >> n;
	rep(i , 1 , n) cin >> p[i] >> s[i];
	cout << EX_CRT(s , p , n) << '\n';
	return 0;
}
\end{lstlisting}

\end{document}
